package com.algorithm.learning.base.二叉树;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/23 23:14
 **/
public class 同一棵二叉树 {

    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 判断两颗树是否是同一颗树
     *
     * 即，两个数值相等，且左右子树结构也相同
     * @param tree1
     * @param tree2
     * @return
     */
    public static boolean isSameTree(Node tree1, Node tree2) {
        // 这里要注意了, ^ 符号表示异或
        // 这里的意思就是如果 tree1为空，但tree2不为空，那(tree1 == null ^ tree2 == null) = true, 也意味着，这两棵树永远不可能相同
        // 同理 tree1不为空，但tree2为空，那(tree1 == null ^ tree2 == null) = true
        if (tree1 == null ^ tree2 == null) {
            return false;
        }
        if (tree1 == null && tree2 == null) {
            return true;
        }
        return tree1.value == tree2.value && isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right);
    }

    public static void main(String[] args) {
        Node tree1 = new Node(1);
        tree1.left = new Node(2);
        tree1.right = new Node(3);
        tree1.left.left = new Node(4);
        tree1.left.right = new Node(5);

        Node tree2 = new Node(1);
        tree2.left = new Node(2);
        tree2.right = new Node(3);
        tree2.left.left = new Node(4);
        tree2.left.right = new Node(5);

        System.out.println(isSameTree(tree1, tree2));
    }
}
